package Sort;

import javax.print.DocFlavor;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.IllegalFormatCodePointException;

public class mergeSort {
    public static void main(String[] args) {
        int[] arr = {1,10,7,4,8,3,2,6,9,5};
        int[] a = new int[arr.length];
        //spilt(arr,0, arr.length - 1,a);
        //merge(arr);
        spiltInsert(arr,0,arr.length,a);
        System.out.println(Arrays.toString(arr));
    }

    //使用非递归实现归并排序
    public static void merge(int[] arr) {
        int n = arr.length;;
        int[] a = new int[n];
        for (int width = 1;width < n ;width *= 2) {
            //[left,right] 分别代表带合并区间的左右边界
            for (int left = 0;left < n; left = left + 2 * width) {
                int right = Math.min(left + 2 * width - 1,n - 1);
                int m = Math.min(left + width - 1,n - 1);
                mergeArr(arr,left,m,m+1,right,a);
            }
            System.arraycopy(a,0,arr,0,n);
        }

    }

    //使用递归实现归并排序
    public static void spilt(int[] arr,int left,int right, int[] a) {
        if (left == right) {
            return;
        }
        //分
        int mid = (left + right) >>> 1;
        spilt(arr,left,mid,a);
        spilt(arr,mid+1,right,a);
        //合
        mergeArr(arr,left,mid,mid + 1,right,a);
        System.arraycopy(a,left,arr,left,right - left + 1);
    }

    //非递归实现两个有序数组合并
    public static void mergeArr(int[] arr,int i,int iEnd,int j,int jEnd,int[] a) {
        int k = i;
        while(i <= iEnd && j <= jEnd) {
            if (arr[i] < arr[j]) {
                a[k] = arr[i];
                i++;
            }else {
                a[k] = arr[j];
                j++;
            }
            k++;
        }
        if (i > iEnd) {
            System.arraycopy(arr,j,a,k,jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(arr,i,a,k,iEnd - i + 1);
        }
    }

    //递归实现两个有序数组合并
    public static void mergeArr(int[] arr,int i,int iEnd,int j, int jEnd,int[] a,int k) {
        if (i > iEnd) {
            System.arraycopy(arr,j,a,k,jEnd - j + 1);
            return;
        }
        if (j > jEnd) {
            System.arraycopy(arr,i,a,k, iEnd - 1 + 1);
            return;
        }

        if (arr[i] < arr[j]) {
            a[k] = arr[i];
            mergeArr(arr,i+1,iEnd,j,jEnd,a,k+1);
        }else {
            a[k] = arr[j];
            mergeArr(arr,i,iEnd,j+1,jEnd,a,k+1);
        }
    }


    //递归归并 + 插入排序
    public static void spiltInsert(int[] arr,int left,int right,int[] a) {
        if (right - left <= 32) {
            insert(arr,left,right);
            return;
        }
        int m = (left + right) >>> 1;
        spiltInsert(arr,left,m,a);
        spiltInsert(arr,m+1,right,a);
        mergeArr(arr,left,m,m+1,right,a);
        System.arraycopy(a,left,arr,left,right-left+1);
    }
    //插入排序
    public static void insert(int[] arr,int left, int right) {
        for (int i = left + 1; i < right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }
}
